1. Technical Field
The present invention relates to an encoder, decoder, encoding method, and decoding method using an LDPC-CC (Low-Density Parity-Check Convolutional Code).
2. Description of the Related Art
In recent years, attention has been attracted to a Low-Density Parity-Check (LDPC) code as an error correction code that provides high error correction capability with a feasible circuit scale. Due to its high error correction capability and ease of implementation, an LDPC code has been adopted in an error correction code for IEEE802.11n high-speed wireless LAN (Local Area Network) systems, digital broadcasting systems, and so forth.
An LDPC code is an error correction code defined by a low-density parity check matrix (that is, a parity check matrix in which there are far fewer 1 elements than 0 elements). An LDPC code is a block code having a block length equal to number of columns N of a parity check matrix.
However, a characteristic of many current communication systems is that communication is based on variable-length packets and frames, as in the case of the Ethernet (registered trademark). A problem with applying an LDPC code, which is a block code, to a system of this kind is, for example, how to make a fixed-length LDPC code block correspond to a variable-length Ethernet (registered trademark) frame. With IEEE802.11n, a wireless LAN standard for which an LDPC code has been adopted, adjustment of the length of a transmission information sequence and an LDPC code block length is performed by applying padding and/or puncturing to a transmission information sequence. However, a problem with this is the necessity of changing the coding rate by means of padding or puncturing, and of performing redundant sequence transmission.
In contrast to this kind of block-wise LDPC code (hereinafter referred to as “LDPC-BC: Low-Density Parity-Check Block Code”), an LDPC-CC allowing encoding and decoding of information sequences with arbitrary length has been investigated (see Non-Patent Document 1).
An LDPC-CC is a convolutional code defined by a low-density parity-check matrix. FIG. 1 shows, as an example, parity check matrix H[0,n]T of an LDPC-CC for which coding rate R=1/2 (=b/c).
With an LDPC-CC, elements h1(m)(t) and h2(m)(t) of parity check matrix H[0,n]T are 0 or 1. Also, all elements other than h1(m)(t) and h2(m)(t) included in parity check matrix H[0,n]T are 0. In FIG. 1, M represents the memory length for an LDPC-CC, and n represents the length of a transmission information sequence. As shown in FIG. 1, a characteristic of a parity check matrix of an LDPC-CC is that it is a parallelogram-shaped matrix in which 1 is placed only in diagonal terms of the matrix and neighboring elements, and the bottom-left and top-right elements of the matrix are zero.
Here, if an example in which coding rate R=1/2 (=b/c) is shown, when h1(0)(t)=1 and h2(0)(t)=1, LDPC-CC encoding is performed by means of equation 1 and equation 2 in accordance with parity check matrix H[0,n]T in FIG. 1.
                    (                  Equation          ⁢                                          ⁢          1                )                                                                      v                      1            ,            t                          =                  u          t                                    [        1        ]                                (                  Equation          ⁢                                          ⁢          2                )                                                                      v                      2            ,            t                          =                                            ∑                              i                =                0                            M                        ⁢                                                            h                  1                                      (                    i                    )                                                  ⁡                                  (                  t                  )                                            ⁢                              u                                  t                  -                  i                                                              +                                    ∑                              i                =                1                            M                        ⁢                                                            h                  2                                      (                    i                    )                                                  ⁡                                  (                  t                  )                                            ⁢                              v                                  2                  ,                                      t                    -                    i                                                                                                          [        2        ]            
Here, ut represents a transmission information sequence, and v1,t and v2,t represent transmission codeword sequences.
FIG. 2 shows an example of a main configuration of an LDPC-CC encoder that executes equation 1 and equation 2. As shown in FIG. 2, LDPC-CC encoder 10 comprises shift registers 11-1 through 11-M and 14-1 through 14-M, weight multipliers 12-0 through 12-M and 13-0 through 13-M, weight control section 16, and modulo 2 adder 15.
Shift registers 11-1 through 11-M and 14-1 through 14-M are registers storing v1,t-i and v2,t-i (where i=0, . . . , M) respectively, and at a timing at which the next input comes in, output a stored value to the adjacent shift register to the right, and newly store a value output from the adjacent shift register to the left.
Weight multipliers 12-0 through 12-M and 13-0 through 13-M switch values of h1(m) and h2(m) to 0 or 1 in accordance with a control signal output from weight control section 16. Based on a parity check matrix stored internally, weight control section 16 outputs the values of h1(m) and h2(m) at that timing to weight multipliers 12-0 through 12-M and 13-0 through 13-M.
Modulo 2 adder 15 performs modulo 2 addition on the outputs of weight multipliers 12-0 through 12-M and 13-0 through 13-M, and calculates v2,t.
By employing this kind of configuration, LDPC-CC encoder 10 can perform LDPC-CC encoding in accordance with a parity check matrix.
A characteristic of an LDPC-CC encoder is that it can be implemented with extremely simple circuitry as compared with the circuitry of an encoder that performs generator matrix multiplication, or an LDPC-BC encoder that performs computation based on backward substitution or forward substitution. Also, since an LDPC-CC is a convolutional code, it is not necessary to divide a transmission information sequence into fixed-length blocks when encoding, and an information sequence of any length can be encoded.
In LDPC-CC decoding, a sum-product algorithm can be applied based on a parity check matrix in the same way as with an LDPC-BC. Therefore, it is not necessary to use a decoding algorithm based on maximum likelihood sequence estimation such as a Viterbi algorithm, and decoding processing can be completed with little processing delay. Furthermore, in Non-Patent Document 1, a decoding algorithm is proposed that takes advantage of the structure of the parity check matrix, in which 1s are arranged in a parallelogram configuration (see Patent Document 1).
When LDPC-CC and LDPC-BC decoding performance are compared using parameters such that the decoder circuit scales are equivalent, LDPC-CC decoding performance are shown to be superior (see Non-Patent Document 1).
Now we consider that an encoder terminates LDPC-CC encoding at an arbitrary length n, and a decoder decodes a corresponding received codeword sequence. In this case, the decoder requires the codeword that encoded transmission information sequences after the n-th bit and shift register states at the end of encoding in order to make probability propagation of the rear c×M bits equivalent to that of the other bits in sum-product decoding.
However, when a transmission information sequence is simply encoded, since encoder shift register states at the end of encoding depend on the transmission information sequence, it is difficult to decide those states uniquely on the receiver side.
If decoding processing is performed on the receiver side based on a received codeword sequence in such a situation, a phenomenon occurs whereby errors increase at the end of a received information sequence obtained after decoding, particularly in the rear c×M bits.
In order to prevent such errors, it is necessary for termination processing (termination) that uniquely decides a terminal state of encoding to be executed on a transmission information sequence.
With a convolutional code conforming to IEEE802.11n, termination is executed by adding “tail bits” comprising the six 0s to the rear of a transmission information sequence when performing encoding. The number of bits in the tail, six, is the same as the number of shift registers in an encoder. In this way, the state of an encoder shift register can be made all-zeros at a point in time at which tail bit input ends. A codeword output when a tail bit is input is necessary for decoding processing on the receiver side, and is therefore transmitted to the receiver side together with a transmission codeword.
In the case of an LDPC-CC, as shown in equation 2, codewords v2,t-i for the past M times are necessary to find codeword v2,t, and therefore shift registers for storing codeword v2,t-i for the past M times are provided in an LDPC-CC encoder. A register storing a transmission information sequence can be set to an all-zero state by making the end of a transmission information sequence a length-M all-zero sequence (termination), but a problem is that it is difficult to set a shift register storing codeword v2,t-i to an all-zero state with only this termination processing.
In Non-Patent Document 2, termination processing is proposed that sets the state of a shift register at the end of encoding to all-zeros by performing encoding after adding a termination sequence to the rear of a transmission information sequence.
In the termination processing proposed in Non-Patent Document 2, a transmission codeword sequence is defined as shown in equation 3. Equation 3 is an example for a case in which coding rate R=1/2. In equation 3, v1×2n is a length-2n codeword sequence obtained by convolutional encoding of a length-n information sequence, x1×2L is a termination codeword sequence obtained by convolutional encoding of a length-L termination sequence, and 01×2M is a length-2M 0-sequence.[v1×2n,x1×2L,01×2M]H′2(n+L+M)×(n+L+M)=01×(n+L+M)  (Equation 3)
Here, termination sequence x1×2L is decided by equation 4 and equation 5.
                                          [                                          v                                  1                  ×                  2                  ⁢                                                                          ⁢                  n                                            ,                              x                                  1                  ×                  2                  ⁢                                                                          ⁢                  L                                            ,                              0                                  1                  ×                  2                  ⁢                                                                          ⁢                  M                                                      ]                    ⁡                      [                                                                                A                                          2                      ⁢                                                                                          ⁢                      n                      ×                      n                                                                                                            B                                          2                      ⁢                                                                                          ⁢                      n                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                                                              0                                          2                      ⁢                                                                                          ⁢                      L                      ×                      n                                                                                                            D                                          2                      ⁢                                                                                          ⁢                      L                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                                                              0                                          2                      ⁢                                                                                          ⁢                      M                      ×                      n                                                                                                            F                                          2                      ⁢                                                                                          ⁢                      M                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                  ]                          =                  0                      1            ×                          (                              n                +                L                +                M                            )                                                          (                  Equation          ⁢                                          ⁢          4                )                                                          ⁢                                            x                              1                ×                2                ⁢                                                                  ⁢                L                                      ⁢                          D                              2                ⁢                                                                  ⁢                L                ×                                  (                                      L                    +                    M                                    )                                                              =                                                    v                                  1                  ×                  2                  ⁢                                                                          ⁢                  n                                            ⁢                              B                                  2                  ⁢                                                                          ⁢                  n                  ×                                      (                                          L                      +                      M                                        )                                                                        =            β                                              (                  Equation          ⁢                                          ⁢          5                )            
The state of a shift register can be set to an all-zero state by encoding a transmission codeword sequence to which such a termination sequence has been added with an LDPC-CC encoder. By having a transceiver-side communication apparatus transmit a transmission codeword that has undergone termination processing in this way to the receiver side, the receiver side decoder can uniquely decide a shift register state at the end of encoding, and performs error correction decoding at a desired level of performance.
FIG. 3 shows a configuration of an LDPC-CC encoder to which a termination sequence generation section that generates termination sequence x1×2L shown in equation 5 has been added. LDPC-CC encoder 20 shown in FIG. 3 comprises termination sequence generation section 17, parity check matrix storage section 18, and switch 19 in addition to the configuration elements of LDPC-CC encoder 10.
Parity check matrix storage section 18 stores a parity check matrix of an LDPC-CC.
Termination sequence generation section 17 generates termination sequence x1×2L in accordance with equation 5, using the parity check matrix stored in parity check matrix storage section 18 and v1,t and v2,t, and outputs obtained termination sequence x1×2L to switch 19.
Switch 19 switches a sequence output to shift register 11-1 to either a transmission information sequence or a termination sequence based on a termination processing control signal. Specifically, switch 19 outputs a transmission information sequence to shift register 11-1 when the termination processing control signal indicates transmission information sequence encoding, and outputs a termination sequence to shift register 11-1 when the termination processing control signal indicates termination processing.
FIGS. 4A and 4B show an LDPC-CC encoder 20 input sequence and output sequence. FIG. 4A shows an input sequence input to LDPC-CC encoder 20, and FIG. 4B shows an output sequence output from LDPC-CC encoder 20. In FIGS. 4A and 4B, a time series runs in the right-to-left direction of each sequence.
An LDPC-CC encoder 20 input sequence is composed of an information sequence comprising n bits, a padding sequence comprising 0 to M bits, and a termination sequence comprising (M+1) bits.
Here, information sequence length n is arbitrary, and therefore when information sequence decoding ends, a weight pattern output to weight multipliers 12-0 through 12-M and 13-0 through 13-M from weight control section 16 differs according to the value of n. This shows that D2L×(L+M) in equation 5 differs according to n. As a result, there are cases in which D2L×(L+M) is and is not full-rank. Consequently, D2L×(L+M) when a termination sequence is found differs according to number of bits n of an information sequence. Thus, in order to make D2L×(L+M) when performing termination processing the same regardless of number of bits n of an information sequence, a padding sequence of K bits (where K=0 to M) is inserted after an information sequence. A padding sequence may be any kind of sequence, as long as it is a sequence known on the encoding side and on the decoding side. For example, an all-zero sequence can be used.
A padding sequence and termination sequence are sequences necessary for termination processing, and since they are only for padding and termination processing use and do not include information of any kind, they constitute information transmission overhead.
In addition to a codeword sequence obtained by encoding an information sequence, an LDPC-CC encoder 20 output sequence also includes a codeword sequence obtained by encoding a padding sequence and termination sequence. As a result, information transmission overhead is (K+M+1)×c bits, where K represents the length of a padding sequence, and c represents the denominator of LDPC-CC coding rate R=b/c.    Patent Document 1: U.S. Patent Application No. 60/682,178 Specification    Non-Patent Document 1: Alberto Jimenez Felstorom, and Kamil Sh. Zigangirov, “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check Matrix,” IEEE Transactions on Information Theory, Vol. 45, No. 6, pp 2181-2191, September 1999.    Non-Patent Document 2: Zhengang Chen, Stephen Bates, and Ziaodai Dong, “Low-Density Parity-Check Convolutional Codes Applied to Packet Based Communication Systems,” Proceeding of IEEE Globecom 2005, pp 1250-1254.    Non-Patent Document 3: Stephen Bates, Duncan G. Elliott, Ramkrishna Swamy, “Termination Sequence Generation Circuits for Low-Density Parity-Check Convolutional Codes,” IEEE Transactions on Circuits and Systems-1: Regular Papers, Vol. 53, No. 9, September 2006.    Non-Patent Document 4: R. D. Gallager, “Low-Density Parity-Check Codes,” Cambridge, Mass.: MIT Press, 1963.    Non-Patent Document 5: M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. Commun., vol. 47., no. 5, pp. 673-680, May 1999.    Non-Patent Document 6: J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Yu Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun., vol. 53., no. 8, pp. 1288-1299, August 2005.    Non-Patent Document 7: Y. Ogawa, “Sum-product decoding of turbo codes,” M. D. Thesis, Dept. Elec. Eng., Nagaoka Univ. of Technology, February 2007.    Non-Patent Document 8: S. Lin, D. J. Jr., Costello, “Error control coding: Fundamentals and applications,” Prentice-Hall.    Non-Patent Document 9: R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello Jr., “LDPC block and convolutional codes based on circulant matrices,” IEEE Trans. Inform. Theory, vol. 50, no. 12, pp. 2966-2984, December 2004.    Non-Patent Document 10: G. Richter, M. Kaupper, and K. Sh. Zigangirov, “Irregular low-density parity-Check convolutional codes based on protographs,” Proceeding of IEEE ISIT 2006, pp1633-1637.